#include <bits/stdc++.h>

class Solution {
public:

    /**
     * @description: 二叉树层序遍历
    */
    vector<vector<int>> levelOrder(TreeNode* root) {

        vector<vector<int>> node_result;
        
        deque<TreeNode*> node_que;
        if(root) node_que.push_back(root);
        vector<int> one_level(node_que.size());

        while(!node_que.empty()){

            int sz = node_que.size();
            one_level.resize(sz);
            for(int i=0; i<sz; i++){
                TreeNode* node = node_que.front();
                node_que.pop_front();
                if(node->left) node_que.push_back(node->left);
                if(node->right) node_que.push_back(node->right);
                one_level[i] = (node->val);
            }
            node_result.push_back(one_level);
        }

        return node_result;
    }

     /**
     * @description: 二叉树遍历
     * @attention: 递归
    */
    vector<int> postorderTraversal(TreeNode* root) {

        vector<int> node_list;
        if(root == nullptr) return node_list;

        //递归
        postorder(root, node_list);
        midorder(root, node_list);
        preorder(root, node_list);
        return node_list;
    }

    void postorder(TreeNode* root, vector<int>& node_list){

      if(root == nullptr) return;
      if(root->left) postorder(root->left, node_list);
      if(root->right) postorder(root->right, node_list);
      node_list.push_back(root->val);
    }

    void midorder(TreeNode* root, vector<int>& node_list){

      if(root == nullptr) return;
      if(root->left) midorder(root->left, node_list);
      node_list.push_back(root->val);
      if(root->right) midorder(root->right, node_list);
    }

    void preorder(TreeNode* root, vector<int>& node_list){

      if(root == nullptr) return;
      node_list.push_back(root->val);
      if(root->left) midorder(root->left, node_list);
      if(root->right) midorder(root->right, node_list);
    }

    /**
     * @description: 二叉树后续遍历
     * @attention: 迭代
    */
    vector<int> postorderTraversal(TreeNode* root) {

        vector<int> node_list;
        if(root == nullptr) return node_list;

        stack<TreeNode*> contianer;
        contianer.push(root);

        while(!contianer.empty()){
            TreeNode* node_ptr = contianer.top();
            contianer.pop();
            node_list.push_back(node_ptr->val);   
            if(node_ptr->left !=nullptr) contianer.push(node_ptr->left);
            if(node_ptr->right !=nullptr) contianer.push(node_ptr->right);
        }

         reverse(node_list.begin(), node_list.end()); // 将结果反转之后就是左右中的顺序了

        return node_list;
    }

    /**
     * @description: 二叉树后续遍历
     * @attention: 迭代
    */
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == nullptr) return result;

        stack<TreeNode*> node_stack;
        TreeNode* curr = root, pre;

        while(node_stack.size() || curr){
          
          while(curr){
            node_stack.push(curr);
            curr = curr->left;
          }
          curr = node_stack.top();
          node_stack.pop();
          if(curr->right == nullptr || pre==curr->right){
            result.push_back(curr->val);
            pre = curr;
            curr = nullptr;
          }
          else{
            node_stack.push(curr);
            curr = curr->right;
          }
        }

        return result;

    }

    /**
     * @description: 二叉树中序遍历
     * @attention: 迭代
    */
    vector<int> inorderTraversal(TreeNode* root) {
        
        vector<int> result;
        if(root == nullptr) return result;

        stack<TreeNode*> node_stack;
        TreeNode* curr = root;

        while(node_stack.size() || curr){

          if(curr) {
            node_stack.push(curr);
            curr = curr->left;
          }
          else {
            curr = node_stack.top();
            node_stack.pop();
            result.push_back(curr->val);
            curr = curr->right;
          }
        }

        return result;
    }

    /**
     * @description: 二叉树前序遍历
     * @attention: 迭代
    */
    vector<int> inorderTraversal(TreeNode* root) {
        
        vector<int> result;
        if(root == nullptr) return result;

        stack<TreeNode*> node_stack;
        node_stack.push(root);


        while(node_stack.size()){

          TreeNode* curr = node_stack.top();
          node_stack.pop();

          result.push_back(curr->val);
          if(curr->right) node_stack.push(curr->right);
          if(curr->left) node_stack.push(curr->left);
          
        }

        return result;
    }
};